题解 CF24D 【Broken robot】

发表于 | 更新于

设状态$f[i][j]$为从坐标$(i,j)$走到最后一行的期望

此时需要分类讨论,由于$f[n]j=0$，所以我们倒着枚举行,也可感性理解为从最后一行走到第x行

当$j=1$时，$f[i][1]=\frac{1}{3}f[i][1]+\frac{1}{3}f[i][2]+\frac{1}{3}f[i+1][1]+1$

当$j=m$时，$f[i][m]=\frac{1}{3}f[i][m]+\frac{1}{3}f[i][m-1]+\frac{1}{3}f[i+1][m]+1$

当$1<j<m$时，$f[i][j]=\frac{1}{4}f[i][j-1]+\frac{1}{4}f[i][j]+\frac{1}{4}f[i][j+1]+\frac{1}{4}f[i+1][j]+1$

然后我们发现这个式子是有后效性的，所以要$dp+$高斯消元。

为了更好高斯消元，我们可以压掉第一维，式子中的$f[i+1]$计为数组$last$。(但我实现上还是用了两维)

经过移项化简后得到：

当$j=1$时，$2f[1]-f[2]=last[i] + 3$

当$j=m$时，$-f[m-1]+2f[m]=last[m]+3$

当$1<j<m$时，$-f[j-1]+3f[j]-f[j+1]=last[j]+4$

由于是倒着枚举，所以$last$数组在转移前已经知道了，这就完全是个高斯消元的式子了，用矩阵表示就会变成下面这个样子

$\begin{bmatrix}2\ &-1\ &0\ &0\ &0\-1\ &3\ &-1\ &0\ &0\0 &-1\ &3\ &-1\ & 0\0\ &0\ &-1\ &3\ &-1\0\ &0\ &0\ &-1\ &2\end{bmatrix}$

用高斯消元显然会T，但是我们发现每行最多只有$3$个非$0$元素,所以我们可以暴力模拟高斯消元求解,最后答案就是$f[x][y]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
double f[1007][1007],a1[1007],a2[1007],a3[1007],c[1007];
//c数组为方程组'='右边的值，a1,a2,a3分别表示一行中三个元素的值，f数组即为转移数组
signed main(){
    int n=read(),m=read(),x=read(),y=read();
    if (m==1){
        printf("%.10lf",2.0*(n-x));
        return 0;
    }
    for (int i=n-1;i>=x;--i){
        for (int j=1;j<=m;++j)c[j]=f[i+1][j]+4.0;
        c[1]-=1.0;c[m]-=1.0;
        a1[1]=0;a2[1]=2.0;a3[1]=-1.0;
        for (int j=2;j<=m-1;++j)a1[j]=-1,a2[j]=3,a3[j]=-1;
        a1[m]=-1;a2[m]=2;a3[m]=0;
        for (int j=2;j<=m;++j){
            double z=a1[j]/a2[j-1];
            a2[j]-=z*a3[j-1];
            c[j]-=c[j-1]*z;
        }
        f[i][m]=c[m]/a2[m];
        for (int j=m-1;j;--j)f[i][j]=(f[i][j+1]+c[j])/a2[j];
    }
    printf("%.10lf",f[x][y]);
}